1. Field of the Invention
The present invention relates to cell flow control techniques employing a backpressure control scheme in an ATM (Asynchronous Transfer Mode) switch, and in particular to a cell flow control method and system in a square-grid expanded ATM switch.
2. Description of Related Art
In some ATM switches having input and output buffers therein, a backpressure controller is provided to perform backpressure control to prevent call overflow in output buffers. Such a backpressure control has been disclosed in many publications. For example, see Japanese Patent Application Unexamined Publication Nos. 10-276206 and P2000-22716A.
There has been proposed a square-grid expanded ATM switch. Hereafter, taking a 2xc3x972 square-grid expanded ATM switch as an example, a conventional cell flow control method applied to the square-grid expanded ATM switch and its disadvantages will be described with reference to FIGS. 1 and 2.
Referring to FIG. 1, the square-grid expanded ATM switch is provided with 2n input ports 901-1 to 901-2n, an input section 911, an output section 921, 2n output ports 931-1 to 931-2n. 
The input section 911 has 2n input modules 912-1 to 912-2n therein. Each of the input modules 912-1 to 912-2n, which will be hereafter denoted by reference numeral 912-i (i=1, 2, . . , 2n), includes input buffers 913-i-1 to 913-i-2n corresponding to respective ones of the 2n output ports 931-i to 931-2n. 
Here, the 2n input ports 901-1 to 901-2n are divided into two input port lines: first input port line (or group) composed of n input ports 901-1 to 901-n; and second input port line (or group) composed of n input ports 901-(n/1) to 901-2n. Similarly, the 2n output ports 931-1 to 931-2n are divided into two output port lines; first output port line (or group) composed of n output ports 931-1 to 931-n; and second output port line (or group) composed of n output ports 931-(n+1) to 931-2n. 
The output section 921 has 2xc3x972 output modules 922-(1,1) 922-(1,2), 922-(2,1), and 922-(2,2) arrayed like a square grid. Each of the output modules will be hereafter denoted by reference numeral 922-(k, h), where k=1, 2 and h=1, 2. In other words, k indicates one of the first and second input port lines and h indicates one of the first and second output port lines. The output section 921 further has two output cell controllers 925-1 and 925-2, each of which will be denoted by reference numeral 925-h. Each output module 922-(k, h) includes n output buffers 923-(k, h)-1 to 923-(k, h)-n and a backpressure controller 924-(k, h).
Each input port 901-i receives a stream of ATM cells from a corresponding incoming line. The input port 901-i checks the header information of a received ATM cell to determine an output port. 931-j (j=1, 2, . . . , 2n) to which the ATM cell is forwarded and then outputs the ATM cell to an input buffer 913-i-j corresponding to the determined output port 931-j.
Each input buffer 913-i-j (i-1 to n, j-1 to n) outputs an ATM cell to an output buffer 923-(1, 1)-j. Each input buffer 913-i-(n+j) (i=1 to n, j=1 to n) outputs an ATM cell to an output buffer 923-(1, 2)-j. Each input buffer 913-(n+i)-j (i=1 to n, j=1 to n) outputs an ATM cell to an output buffer 923-(2, 1)-j. Each input buffer 913-(n+i)-(n+j) (i=1 to n, j=1 to n) outputs an ATM cell to an output buffer 923-(2, 2)-j.
Accordingly, output modules 922-(k, h) on the same row handle ATM cells received at the same input port line and output modules 922-(k, h) on the same column handle ATM cells to be forwarded to the same output port line. In other words, the output modules 922-(k, h) are arrayed in a row for each input port line and in a column for each output port line.
In this example, the output modules 922-(1, h) on the first row belong to the first input port line and the output modules 922-(2, h) on the second row belong to the second input port line. The output modules 922-(k, 1) on the first column belong to the first output port line and the output modules 922-(k, 2) on the second column belong to the second output port line.
In association with this, the first input port line includes the input ports 901-1 to 901-n, input modules 912-1 to 912-n, input buffers 913-1-1 to 913-1-2n, . . . , 913-n-1 to 913-n-2n, and output buffers 923-(1,1)-1 to 923-(1,1)-n, 923-(1,2)-1 to 923-(1,2)-n. The second input port line includes the input ports 901-(n+1) to 901-2n, input modules 912-(n+1) to 912-2n, input buffers 913-(n+1)-1 to 913-(n+1)-2n, . . . 913-2n-1 to 913-2n-2n, and output buffers 923-(2,1)-1 to 923-(2,1)-n, 923-(2,2)-1 to 923-(2,2)-n.
Further, the first output port line includes the output ports 931-1 to 931-n, output cell controller 925-1, output buffers 923-(1,1)-1 to 923-(1,1)-n, 923-(2,1)-1 to 913-(2,1)-n, and input buffers 913-1-1 to 913-1-n, . . . , 913-2n-1 to 913-2n-n. The second output port line includes the output ports 931-(n+1) to 931-2n, output cell controller 925-2, output buffers 923-(1,2)-1 to 923-(1,2)-n, 923-(2,2)-1 to 913(2,2)-n, and input buffers 913-1-(n+1) to 913-1-2n, . . . , 913-2n-(n+1) to 913-2n-2n. 
ATM cells read out from the output buffer 923-(1,1)-j (j=1 to n) are forwarded to a corresponding outgoing line through the output cell controller 925-1 and the output port 931-j. ATM cells read out from the output buffer 923-(1,2)-j (j=1 to n) are forwarded to a corresponding outgoing line through the output cell controller 925-2 and the output port 931-(n+1). ATM cells read out from the output buffer 923-(2,1)-j (j=1 to n) are forwarded to a corresponding outgoing line through the output cell controller 925-1 and the output port 931-j. ATM cells read out from the output buffer 923-(2,2)-j (n=1 to n) are forwarded to a corresponding outgoing line through the output cell controller 925-2 and the output port 931-(n/j).
The output cell controller 925-1 performs arbitration of forwarding ATM cells from the output buffer 923-(1, 1)-(jxe2x88x921 to n) to the output port 931-j and ATM cells from the output buffer 923-(2,1)-j (i=1 to n) to the output port 931-j so as to avoid contention for the output port 931-j. The output cell controller 925-2 performs arbitration of forwarding ATM cells from the output buffer 923-(1,2)j (j=1 to n) to the output port 931-(n+j) and ATM cells from the output buffer 923-(2,2)-j (jxe2x88x921 to n) to the output port 931-(n+j) so as to avoid contention for the output port 931-(n+j),
In the above ATM switch of FIG. 1, a conventional backpressure-type cell flow control system will be described hereafter.
Referring to FIG. 2, the backpressure controller 924-(1,1) determines whether an occupation rate of ATM cells in the output buffer 923-(1, 1)-j (jxe2x88x921 to n) exceeds a threshold and, if the occupation rate exceeds the threshold, then outputs a backpressure control signal 951-(1,1)-j to the input buffer 913-i-j (i=1 to n). The backpressure controller 924-(1,2) determines whether an occupation rate of ATM cells in the output buffer 923-(1,2)-j (jxe2x88x921 to n) exceeds a threshold and, if the occupation rate exceeds the threshold, then outputs a backpressure control signal 951-(1,2)-j to the input buffer 913-i-(n+j) (i=1 to n). The backpressure controller 924-(2,1) determines whether an occupation rate of ATM cells in the output buffer 923-(2, 1)-j (j=1 to n) exceeds a threshold and, if the occupation rate exceeds the threshold, then outputs a backpressure control signal 951-(2,1)-j to the input buffer 913-(n+i)-j (i=1 to n). The backpressure controller 924-(2,2) determines whether an occupation rate of ATM cells in the output buffer 923-(2,2)-j (j=1 to n) exceeds a threshold and, if the occupation rate exceeds the threshold, then outputs a backpressure control signal 951-(2,2)-j to the input buffer 913-(n+i)-(n+j) (i=1 to n).
When receiving the backpressure control signal 951(1,1)-j, the input buffer 913-i-i (i=1 to n) stops outputting an ATM cell to the output buffer 923-(1,1)-j. When receiving the backpressure control signal 951-(1,2)-j, the input buffer 913-i-(n+j) (i=1 to n) stops outputting an ATM cell to the output buffer 923-(1,2)-j. When receiving the backpressure control signal 951-(2,1)-j, the input buffer 913-(n+i)-j (i=1 to n) stops outputting an ATM cell to the output buffer 923-(2,1)-j. When receiving the backpressure control signal 951-(2,2)-j, the input buffer 913-(n+i)-(n+j) (i=1 to n) stops outputting an ATM cell to the output buffer 923-(2,2)-j. In this manner, ATM cells are prevented from overflowing the output buffer 923-(h, m))-j (h=1, 2, m=1, 2, j=1 to n).
However, the above backpressure-type cell flow control has the following disadvantages.
In the case where the backpressure controller 924-(1,1) determines that an overflow occurs in the output buffer 923-(1,1)-1 for example, the backpressure control signal 951-(1,1)-1 causes the input buffer 913-i-1 (i=1 to n) to be inhibited from outputting ATM cells to the output buffer 923-(1, 1)-1. At this time, if no overflow occurs in the output buffer 923-(2,1)-1, then the backpressure controller 924-(2,1) does not output any backpressure control signal 951-(2,1)-1, so that the input buffer 913-(n+i)-1 (i=1 to n) is not inhibited from outputting ATM cells to the output buffer 923-(2, 1)-1.
Therefore, oven though these ATM cells are to be forwarded to the same output port 931-1, the ATM cells stored in the input buffer 913-i-1 are inhibited and the ATM cells stored in the input buffer 913-(n+i)-1 are permitted. Similarly, even though ATM cells are to be forwarded to the same output port 931-j (j=1 to 2n), the ATM cells stored in the input buffer 913-i-j (i=1 to 2n) are inhibited and the ATM cells stored in the input buffer 912-(n+i)-j are permitted.
In other words, an unfair backpressure-type cell flow control is performed between the first input port line including input ports 901-1 to 901-n and the second input port line including input ports 901-(n+1) to 901-2n. 
Therefore, an object of the present invention is to provide a backpressure-type cell flow control method and system to a square-grid expanded ATM switch achieving fair cell flow control between input port lines.
According to an aspect of the present invention, a flow control system in a square-grid expanded switch having an array of output buffer modules having a plurality of rows and columns, wherein one output port is associated with a plurality of output buffers each belonging to different rows and same column, the system includes: a backpressure controller provided in each of the output buffer modules for generating a backpressure control signal when an amount of data stored in an output buffer included in a corresponding output buffer module exceeds a predetermined threshold, to avoid an overflow of the output buffer; and a common backpressure generator provided in each of the output buffer modules, for generating a common backpressure control signal when a backpressure control signal is generated by at least one of backpressure controllers provided in output buffer modules belonging to a corresponding column and outputs the common backpressure control signal to a plurality of input buffers storing data to be forwarded to an output port associated with the output buffer.
According to another aspect of the present invention, in a square-grid expanded swatch comprising: Mxc3x97N input ports, where M and N are integers; Mxc3x97N output ports; Mxc3x97N input modules corresponding to respective ones of the Mxc3x97N input ports, each of the input modules including Mxc3x97N input buffers corresponding to respective ones of the Mxc3x97N output ports; an Mxc3x97M array to output butter modules, wherein M rows of the array are associated with respective ones of M input port groups obtained by dividing the Mxc3x97N input ports by N, M columns of the array are associated with respective ones of M output port groups obtained by dividing the Mxc3x97N output ports by N, and each of the output buffer modules includes N output buffers, wherein each of the Mxc3x97N output ports is associated with a corresponding output buffer included in each of M output buffer modules on a corresponding column, wherein each of the N output buffers is associated with N corresponding input buffers included in respective ones of N input modules of a corresponding input port group, the system includes: a backpressure controller provided in each of the output buffer modules, wherein the backpressure controller generates a backpressure control signal when an amount of data stored in each output buffer included in a corresponding output buffer module exceeds a predetermined threshold, to avoid an overflow of the output buffer; and a common backpressure generator provided in each of the output buffer modules, wherein the common backpressure generator generates a common backpressure control signal when a backpressure control signal is generated by at least one of backpressure controllers provided in output buffer modules belonging to a corresponding column and outputs the common backpressure control signal to Mxc3x97N input buffers associated with the output buffer and (Xxe2x88x921) corresponding output buffers included in respective ones of (Mxe2x88x921) output buffer modules belonging to the corresponding column.
The common backpressure generator may be an array of OR gates connected to the backpressure controller, wherein each of the OR gates combines the backpressure control signal, generated by the backpressure controller and another backpressure control signal generated by another backpressure controller belonging in the corresponding column to produce the common backpressure control signal and outputs it to the N input buffers associated with the output buffer and a corresponding OR gate of another array of OR gates connected to another backpressure controller belonging in the corresponding column.
The common backpressure generator may be an array of maximum value detectors connected to the backpressure controller, wherein each of the maximum value detectors detects a maximum backpressure control signal among backpressure control signals generated by the backpressure controller and other backpressure controllers belonging in the corresponding column to output the maximum backpressure control signal as the common backpressure control signal to the N input buffers associated with the output buffer and a corresponding maximum value detector of another array of maximum value detectors connected to another backpressure controller belonging in the corresponding column.